#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;

//01背包
//https://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e?tpId=230&tqId=2032484&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196
//dp数组常规解法
//dp[i][k] 表示在前i个物品中挑选不超过k重量的物品
//const int N = 1010;
//int n = 0, V = 0;
//int v[N]; //体积
//int u[N]; //价值
//int dp[N][N];
//
////dp[i][k] 表示从前i个物品中挑选体积不超过k的物品，所能挑选价值最大的
//
//int main() {
//    int a, b;
//    while (cin >> n >> V) {
//        for (int i = 1; i <= n; ++i)
//            cin >> v[i] >> u[i];
//
//        //至多能装多大价值的物品
//        for (int i = 1; i <= n; ++i) //价值从1开始
//            for (int k = 1; k <= V; ++k) //体积从1开始
//            {
//                dp[i][k] = dp[i - 1][k]; //如果不选该物品 则此时价值是前i-1个物品中挑选体积不超过k的总价值
//                //如果选择该物品 则此物品必须满足 k-v[i]>=0 否则装不下
//                //当可以装下时 我们需要知道前i-1个物品中 体积不超过k-v[i]的最大价值(如果不是k-v[i] 则体积就可能超过k了)
//                if (k - v[i] >= 0) dp[i][k] = max(dp[i][k], dp[i - 1][k - v[i]] + u[i]);
//            }
//        cout << dp[n][V] << endl;
//
//        //背包恰好装满
//        //首先当背包恰好装满 可能出现无法装满的情况 为了区别于没有装然后物品时价值为0
//        //我们约定dp[i][k]为-1时表示无法选择
//        //所以 当价值为0时 无论选什么物品总价值都是0 当体积为0时 根本无法凑出刚好装满的情况 即第一行全为-1
//        for (int i = 1; i <= V; ++i) dp[0][i] = -1;
//
//        for (int i = 1; i <= n; ++i) //价值从1开始
//            for (int k = 1; k <= V; ++k) //体积从1开始
//            {
//                dp[i][k] = dp[i - 1][k]; //当上一个物品无法选择 则不选择当前物品 也是无法选择
//                //如果上一个物品无法选择 不能强行相加 会出现错误计算
//                if (k - v[i] >= 0 && dp[i - 1][k - v[i]] != -1) dp[i][k] = max(dp[i][k], dp[i - 1][k - v[i]] + u[i]);
//            }
//        cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
//
//    }
//}

//优化 滚动数组优化空间
//dp[i][k] 表示在前i个物品中挑选不超过k重量的物品
//const int N = 1010;
//int n = 0, V = 0;
//int v[N]; //体积
//int u[N]; //价值
//int dp[N];
//
//int main() {
//    int a, b;
//    while (cin >> n >> V) {
//        for (int i = 1; i <= n; ++i)
//            cin >> v[i] >> u[i];
//
//        for (int i = 1; i <= n; ++i)
//            for (int k = V; k >= 1; --k)
//                if (k - v[i] >= 0) dp[k] = max(dp[k], dp[k - v[i]] + u[i]);
//
//        cout << dp[V] << endl;
//
//
//        for (int i = 1; i <= V; ++i) dp[i] = -1;
//
//        for (int i = 1; i <= n; ++i)
//            for (int k = V; k >= 1; --k)
//                if (k - v[i] >= 0 && dp[k - v[i]] != -1) dp[k] = max(dp[k], dp[k - v[i]] + u[i]);
//
//        cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
//    }
//}



//分割等和子集
//https://leetcode.cn/problems/partition-equal-subset-sum/
// class Solution {
// public:
//     bool canPartition(vector<int>& nums) {
//       int n = nums.size();

//       //计算总和
//       int sum = 0;
//       for(const auto& num:nums) sum += num;
//       //如果sum/2为奇数 则我们不可能凑出两个相等的组
//       if(sum%2) return false; 
//       sum /= 2;

//       //vv[i][k]:表示在前i个数字中凑k(n%2) 是否可以凑出
//       vector<vector<bool>> vv(n+1,vector<bool>(sum+1));
//       //注意 
//       //在前0个数字中凑出k是不可能的 所以第一行为false(vv[0][0]除外)
//       //在前i个数字中凑出0是可以的 全部不选即可 即从[0][0]-[n][0]全部是true
//       //当我们可以在数组中凑出k/2
//       for(int i = 0;i<=n;++i) vv[i][0] = true;
//       for(int i = 1;i<=n;++i)
//         for(int k = 1;k<=sum;++k)
//         {
//           //不选当前数字
//           vv[i][k] = vv[i-1][k];
//           //选择当前数字
//           if(k >= nums[i-1]) vv[i][k] = vv[i][k] || vv[i-1][k-nums[i-1]];
//         }
//       return vv[n][sum];
//     }
// };

//优化空间
// class Solution {
// public:
//     bool canPartition(vector<int>& nums) {
//       int n = nums.size();
//       int sum = 0;
//       for(const auto& num:nums) sum += num;
//       if(sum%2) return false; 
//       sum /= 2;

//       vector<bool> vv(sum+1);

//       vv[0] = true;
//       for(int i = 1;i<=n;++i)
//         for(int k = sum;(k >= nums[i-1]) && k>0;--k)
//           vv[k] = vv[k] || vv[k-nums[i-1]];
        
//       return vv[sum];
//     }
// };


//目标和
//https://leetcode.cn/problems/target-sum/
// class Solution {
// public:
//     int findTargetSumWays(vector<int>& nums, int target) {
//         int n = nums.size();
//         int sum = 0;
//         for(const auto& x:nums) sum += x;
//         int aim = (sum + target) / 2;
//         if (aim < 0 || (sum + target) % 2 == 1) return false; //如果加起来为负数或为奇数 则不可能选出数组
//         //设 a为全部选的正数  b为全部选择的负数
//         //   则a - (-b)=target
//         //     a + b  = nums和
//         //   则 2a = target+nums    a=(target+nums)/2
//         //vv[i][k]:表示在前i个数中选择能组成k的数的选法
//         //一个数如果不选 则是在前i-1个数中选择可以组成为k的数 即vv[i][k] = vv[i-1][k]
//         //一个数如果选 则这个数必须是 k>nums[i] vv[i][k] += vv[i-1][k-nums[i]] 如果选和不选都可以 则这两个都算 所以要+=
//         vector<vector<int>> vv(n+1,vector<int>(aim+1));
//         //从前0个数中无法选择为k的数 从前i个数中选择为0的数 只需要都不选即可
//         //只需要初始化vv[0][0] 即可
//         vv[0][0] = 1;

//         for(int i = 1;i<=n;++i)
//             for(int k = 0;k<=aim;++k)
//             {
//                 vv[i][k] = vv[i-1][k];
//                 if(k-nums[i-1]>=0) vv[i][k] += vv[i-1][k-nums[i-1]];
//             }

//         return vv[n][aim];
//     }
// };
//优化空间
// class Solution {
// public:
//     int findTargetSumWays(vector<int>& nums, int target) {
//         int n = nums.size();
//         int sum = 0;
//         for(const auto& x:nums) sum += x;
//         int aim = (sum + target) / 2;
//         if (aim < 0 || (sum + target) % 2 == 1) return false; 

//         vector<int> vv(aim+1);
//         vv[0]= 1;

//         for(int i = 1;i<=n;++i)
//             for(int k = aim;k>=0;--k)
//                 if(k-nums[i-1]>=0) vv[k] += vv[k-nums[i-1]];

//         return vv[aim];
//     }
// };